package com.demo.java.OD351_400.OD389;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【聚餐地点or欢乐的周末(C卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146243069
 */
public class OdMain {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 输入地图的行和列
        int x = sc.nextInt();
        int y = sc.nextInt();

        int[][] maze = new int[x][y];
        List<int[]> hwCoords = new ArrayList<>();
        List<int[]> cgCoords = new ArrayList<>();

        // 输入地图内容
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                maze[i][j] = sc.nextInt();  // 读取地图元素
                if (maze[i][j] == 2) {  // 小孩1的起点
                    hwCoords.add(new int[]{i, j});
                } else if (maze[i][j] == 3) {  // 小孩2的起点
                    cgCoords.add(new int[]{i, j});
                }
            }
        }

        // 获取小孩1和小孩2的起点坐标
        int[] xh = hwCoords.get(0);
        int[] xw = hwCoords.get(1);

        // 记录可以同时到达的目标点数量
        int res = 0;

        // 遍历所有目标点
        for (int[] guan : cgCoords) {
            int[][] tempMaze = copyMaze(maze);
            int endX = guan[0];
            int endY = guan[1];

            // 检查小孩1是否能到达该目标点
            if (canReachEnd(xh[0], xh[1], tempMaze, endX, endY) == 1) {
                tempMaze = copyMaze(maze);

                // 检查小孩2是否能到达该目标点
                if (canReachEnd(xw[0], xw[1], tempMaze, endX, endY) == 1) {
                    res++;  // 如果两个小孩都能到达该目标点，计数
                }
            }
        }

        // 输出结果
        System.out.println(res);
    }

    // 创建迷宫的副本
    public static int[][] copyMaze(int[][] maze) {
        int rows = maze.length;
        int cols = maze[0].length;
        int[][] copy = new int[rows][cols];

        // 复制迷宫内容
        for (int i = 0; i < rows; i++) {
            System.arraycopy(maze[i], 0, copy[i], 0, cols);
        }
        return copy;
    }

    // 判断是否可以到达目标点
    public static int canReachEnd(int x, int y, int[][] maze, int endX, int endY) {
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};  // 四个方向：上、下、左、右

        // 如果当前点就是目标点
        if (x == endX && y == endY) {
            return 1;
        }

        // 遍历四个方向
        for (int[] dir : directions) {
            int newX = x + dir[0];
            int newY = y + dir[1];

            // 判断新位置是否有效且不是障碍物
            if (isValidPosition(newX, newY, maze) && maze[newX][newY] != 1) {
                maze[x][y] = 1;  // 标记当前位置已访问
                if (canReachEnd(newX, newY, maze, endX, endY) == 1) {
                    return 1;
                }
            }
        }

        return 0;  // 如果无法到达目标点
    }

    // 判断当前位置是否有效
    public static boolean isValidPosition(int x, int y, int[][] maze) {
        int rows = maze.length;
        int cols = maze[0].length;
        return x >= 0 && x < rows && y >= 0 && y < cols;
    }
}